#include <memory>
#include <utility>
#include <queue>
#include <variant>
#include <functional>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <iostream>

namespace CAS {

// 前向声明
class Variable;    // 变量
class Constant;    // 常数
class Integer;     // 整数
class UnaryExpr;   // 一元表达式
class BinaryExpr;  // 二元表达式

// 表达式类型定义（统一使用 shared_ptr）
using Number = std::variant<
    std::monostate,             // 空表达式或错误
    Variable,
    Constant,
    Integer,
    std::shared_ptr<UnaryExpr>,
    std::shared_ptr<BinaryExpr>
>;

// 具体声明
class Variable {
 public:
    std::string name;
    explicit Variable(std::string name) : name(std::move(name)) {}
    bool operator==(const Variable& other) const {
        return this->name == other.name;
    }
};

class Constant {
 public:
    enum Type {
        E,
        Pi,
    } type;
    explicit Constant(Type type) : type(type) {}
    bool operator==(const Constant& other) const {
        return this->type == other.type;
    }
};

class Integer {
 public:
    int64_t value;  // 使用 int64_t 支持负数
    explicit Integer(int64_t value) : value(value) {}
    bool operator==(const Integer& other) const {
        return this->value == other.value;
    }
};

class UnaryExpr {
 public:
    enum Op {
        Ln,
        Sin,
        Cos,
        Tan,
        ArcSin,
        ArcCos,
        ArcTan,
    } op;
    Number operand;
    UnaryExpr(Op op, Number operand) : op(op), operand(operand) {}
    bool operator==(const UnaryExpr& other) const {
        return this->op == other.op && this->operand == other.operand;
    }
};

class BinaryExpr {
 public:
    enum Op {
        Add,
        Sub,
        Mul,
        Div,
        Pow,
        Root,
        Log,
    } op;
    Number left;
    Number right;
    BinaryExpr(Op op, Number left, Number right) : op(op), left(left), right(right) {}
    bool operator==(const BinaryExpr& other) const {
        return this->op == other.op &&
               this->left == other.left &&
               this->right == other.right;
    }
};

// Number 比较操作符
bool operator==(const Number& a, const Number& b) {
    if (a.index() != b.index()) return false;
    return std::visit([&](const auto& va, const auto& vb) -> bool {
        using T = std::decay_t<decltype(va)>;
        using U = std::decay_t<decltype(vb)>;
        if constexpr (std::is_same_v<T, U>) {
            if constexpr (std::is_same_v<T, std::shared_ptr<UnaryExpr>>) {
                return *va == *vb;  // 解引用后比较内容
            } else if constexpr (std::is_same_v<T, std::shared_ptr<BinaryExpr>>) {
                return *va == *vb;  // 解引用后比较内容
            } else {
                return va == vb;
            }
        } else {
            return false;
        }
    }, a, b);
}

// 一元运算符转字符串
std::string to_string(UnaryExpr::Op op) {
    static const std::unordered_map<UnaryExpr::Op, std::string> op_names = {
        {UnaryExpr::Op::Sin, "sin"}, {UnaryExpr::Op::Cos, "cos"}, {UnaryExpr::Op::Tan, "tan"},
        {UnaryExpr::Op::ArcSin, "arcsin"}, {UnaryExpr::Op::ArcCos, "arccos"}, {UnaryExpr::Op::ArcTan, "arctan"},
        {UnaryExpr::Op::Ln, "ln"},
    };
    return op_names.at(op);
}

// 二元运算符转字符串
std::string to_string(BinaryExpr::Op op) {
    static const std::unordered_map<BinaryExpr::Op, std::string> op_names = {
        {BinaryExpr::Op::Add, "+"}, {BinaryExpr::Op::Sub, "-"}, {BinaryExpr::Op::Mul, "*"},
        {BinaryExpr::Op::Div, "/"}, {BinaryExpr::Op::Pow, "^"}, {BinaryExpr::Op::Root, "root"},
        {BinaryExpr::Op::Log, "log"},
    };
    return op_names.at(op);
}

// 变量转字符串
std::string to_string(const Variable& v) {
    return v.name;
}

// 常数转字符串
std::string to_string(const Constant& c) {
    static const std::unordered_map<Constant::Type, std::string> const_names = {
        {Constant::Type::E, "e"}, {Constant::Type::Pi, "π"}
    };
    return const_names.at(c.type);
}

// 整数转字符串
std::string to_string(const Integer& c) {
    return std::to_string(c.value);
}

std::string to_string(const Number& num) {
    return std::visit([&](const auto& value) -> std::string {
        using T = std::decay_t<decltype(value)>;
        if constexpr (std::is_same_v<T, std::monostate>) {
            return "undefined";
        } else if constexpr (std::is_same_v<T, Variable>) {
            return to_string(value);
        } else if constexpr (std::is_same_v<T, Constant>) {
            return to_string(value);
        } else if constexpr (std::is_same_v<T, Integer>) {
            return to_string(value);
        } else if constexpr (std::is_same_v<T, std::shared_ptr<UnaryExpr>>) {
            return to_string(value->op) + "(" + to_string(value->operand) + ")";
        } else if constexpr (std::is_same_v<T, std::shared_ptr<BinaryExpr>>) {
            return "(" + to_string(value->left) + to_string(value->op) + to_string(value->right) + ")";
        }
        return "";
    }, num);
}

// 规则基类
class Rule {
 public:
    virtual bool match(const CAS::Number& expr) const = 0;
    virtual CAS::Number apply(CAS::Number expr) const = 0;
};

class RuleManager {
 private:
    std::vector<std::shared_ptr<Rule>> rules;
 public:
    void addRule(std::shared_ptr<Rule> rule) {
        rules.push_back(rule);
    }

    std::vector<CAS::Number> applyAllRules(const CAS::Number& expr) const {
        std::vector<CAS::Number> nextStates;
        bool matched = false;
        for (const auto& rule : rules) {
            if (rule->match(expr)) {
                nextStates.push_back(rule->apply(expr));
                matched = true;
            }
        }
        if (!matched) {
            nextStates.push_back(expr);
        }

        if (auto* unaryPtr = std::get_if<std::shared_ptr<UnaryExpr>>(&expr)) {
            auto unary = *unaryPtr;
            auto newOperands = applyAllRules(unary->operand);
            for (const auto& newOperand : newOperands) {
                auto newExpr = std::make_shared<UnaryExpr>(unary->op, newOperand);
                nextStates.push_back(newExpr);
            }
        } else if (auto* binaryPtr = std::get_if<std::shared_ptr<BinaryExpr>>(&expr)) {
            auto binary = *binaryPtr;
            auto newLefts = applyAllRules(binary->left);
            auto newRights = applyAllRules(binary->right);
            for (const auto& newLeft : newLefts) {
                for (const auto& newRight : newRights) {
                    for (const auto& rule : rules) {
                        auto newExpr = std::make_shared<BinaryExpr>(binary->op, newLeft, newRight);
                        if (rule->match(newExpr)) {
                            nextStates.push_back(rule->apply(newExpr));
                        }
                    }
                }
            }  // ???
        }

        return nextStates;
    }
};

class RuleEngine {
 public:
    struct State {
        CAS::Number expr;               // 当前表达式
        int cost;                       // 当前状态的代价（字符串长度）
        std::string key;                // 当前节点
        std::shared_ptr<State> parent;  // 父状态（用于回溯路径，目前没用）

        State(const CAS::Number& e, int c, const std::shared_ptr<State>& p = nullptr)
            : expr(e), cost(c), key(to_string(e)), parent(p) {}
    };

    // 启发式函数（仅作示范，未使用）
    static int heuristic(const CAS::Number& expr) {
        return to_string(expr).length();
    }

    // 检测最简
    static bool isSimplified(const CAS::Number& expr) {
        // 示例：最简表达式是长度最短的
        return to_string(expr).length() <= 5;
    }

    static CAS::Number aStarSimplify(const CAS::Number& initialExpr, 
                                     const RuleManager& ruleManager,
                                     const std::function<int(const CAS::Number&)>& heuristic) {
        // 优先队列：按 f(n) = g(n) + h(n) 排序
        std::priority_queue<std::pair<int, std::shared_ptr<State>>,
                            std::vector<std::pair<int, std::shared_ptr<State>>>,
                            std::greater<>> openQueue;

        std::unordered_set<std::string> closedSet; // 已访问的状态
        auto startState = std::make_shared<State>(initialExpr, 0);
        openQueue.emplace(heuristic(initialExpr) + 0, startState);

        while (!openQueue.empty()) {
            auto currentPair = openQueue.top();
            auto currentState = currentPair.second;
            openQueue.pop();

            // 判断是否是目标状态（例如：表达式长度最短）
            if (isSimplified(currentState->expr)) {
                return currentState->expr;
            }

            // 避免重复访问
            if (closedSet.count(currentState->key)) continue;
            closedSet.insert(currentState->key);

            // 应用所有规则生成新状态
            for (const auto& nextExpr : ruleManager.applyAllRules(currentState->expr)) {
                auto nextKey = to_string(nextExpr);
                if (closedSet.count(nextKey)) continue;

                int newCost = currentState->cost + 1; // 假设每步代价为 1
                auto nextState = std::make_shared<State>(nextExpr, newCost, currentState);
                int f = newCost + heuristic(nextExpr);
                openQueue.emplace(f, nextState);
            }
        }

        return initialExpr; // 如果没有找到更优路径，返回原表达式
    }
};

// 1 + 1 -> 2
class AddIntRule : public Rule {
public:
    static bool is_integer(const Number& n) {
        return std::holds_alternative<Integer>(n);
    }

    bool match(const Number& expr) const override {
        if (auto* binPtr = std::get_if<std::shared_ptr<BinaryExpr>>(&expr)) {
            auto bin = binPtr->get();
            if (bin && bin->op == BinaryExpr::Op::Add &&
                is_integer(bin->left) && is_integer(bin->right)) {
                return true;
            }
        }
        return false;
    }

    Number apply(Number expr) const override {
        if (auto* binPtr = std::get_if<std::shared_ptr<BinaryExpr>>(&expr)) {
            auto bin = binPtr->get();
            if (bin && bin->op == BinaryExpr::Op::Add &&
                is_integer(bin->left) && is_integer(bin->right)) {
                auto left = std::get<Integer>(bin->left);
                auto right = std::get<Integer>(bin->right);
                return Integer(left.value + right.value); // 直接返回简化后的整数
            }
        }
        return expr;
    }
};

// x + 0 -> x
class AddZeroRule : public Rule {
public:
    static bool is_zero(const Number& n) {
        if (auto* v = std::get_if<Integer>(&n)) {
            return v->value == 0;
        }
        return false;
    }

    bool match(const Number& expr) const override {
        if (auto* binPtr = std::get_if<std::shared_ptr<BinaryExpr>>(&expr)) {
            auto bin = binPtr->get();
            if (bin && bin->op == BinaryExpr::Op::Add && is_zero(bin->right)) {
                return true;
            }
        }
        return false;
    }

    Number apply(Number expr) const override {
        if (auto* binPtr = std::get_if<std::shared_ptr<BinaryExpr>>(&expr)) {
            auto bin = binPtr->get();
            if (bin && bin->op == BinaryExpr::Op::Add && is_zero(bin->right)) {
                return bin->left;
            }
        }
        return expr;  // 匹配失败，返回原表达式
    }
};

// x * 0 -> 0
class MulZeroRule : public Rule {
public:
    static bool is_zero(const Number& n) {
        if (auto* v = std::get_if<Integer>(&n)) {
            return v->value == 0;
        }
        return false;
    }

    bool match(const Number& expr) const override {
        if (auto* binPtr = std::get_if<std::shared_ptr<BinaryExpr>>(&expr)) {
            auto bin = binPtr->get();
            if (bin && bin->op == BinaryExpr::Op::Mul && is_zero(bin->right)) {
                return true;
            }
        }
        return false;
    }

    Number apply(Number expr) const override {
        if (auto* binPtr = std::get_if<std::shared_ptr<BinaryExpr>>(&expr)) {
            auto bin = binPtr->get();
            if (bin && bin->op == BinaryExpr::Op::Mul && is_zero(bin->right)) {
                return Integer(0);
            }
        }
        return expr;  // 匹配失败，返回原表达式
    }
};

// a + b = b + a
class CommutativeRule : public Rule {
 public:
    bool match(const Number& expr) const override {
        if (auto* binPtr = std::get_if<std::shared_ptr<BinaryExpr>>(&expr)) {
            auto bin = binPtr->get();
            if (bin && (bin->op == BinaryExpr::Op::Add || bin->op == BinaryExpr::Op::Mul)) {
                return true;
            }
        }
        return false;
    }

    Number apply(Number expr) const override {
        if (auto* binPtr = std::get_if<std::shared_ptr<BinaryExpr>>(&expr)) {
            auto bin = binPtr->get();
            if (bin && (bin->op == BinaryExpr::Op::Add || bin->op == BinaryExpr::Op::Mul)) {
                return std::make_shared<BinaryExpr>(bin->op, bin->right, bin->left);
            }
        }
        return expr;  // 匹配失败，返回原表达式
    }
};

// c * (a + b) = ac + bc
class DistributionRule : public Rule {
 public:
    bool match(const Number& expr) const override {
        if (auto* binPtr = std::get_if<std::shared_ptr<BinaryExpr>>(&expr)) {
            auto bin = binPtr->get();
            // 检测外层的乘号
            if (bin && bin->op == BinaryExpr::Op::Mul) {
                auto left = bin->left;
                auto right = bin->right;
                // 检测右侧是否为加法
                if (auto* rightBinPtr = std::get_if<std::shared_ptr<BinaryExpr>>(&right)) {
                    auto rightBin = rightBinPtr->get();
                    if (rightBin && rightBin->op == BinaryExpr::Op::Add) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    Number apply(Number expr) const override {
        if (auto* binPtr = std::get_if<std::shared_ptr<BinaryExpr>>(&expr)) {
            auto bin = binPtr->get();
            // 检测外层的乘号
            if (bin && bin->op == BinaryExpr::Op::Mul) {
                auto left = bin->left;
                auto right = bin->right;
                // 检测右侧是否为加法
                if (auto* rightBinPtr = std::get_if<std::shared_ptr<BinaryExpr>>(&right)) {
                    auto rightBin = rightBinPtr->get();
                    if (rightBin && rightBin->op == BinaryExpr::Op::Add) {
                        return std::make_shared<BinaryExpr>(BinaryExpr::Op::Add, std::make_shared<BinaryExpr>(bin->op, left, rightBin->left), std::make_shared<BinaryExpr>(bin->op, left, rightBin->right));
                    }
                }
            }
        }
        return expr;  // 匹配失败，返回原表达式
    }
};

}  // namespace CAS